package someTestExcemple.huaweiOd.string;

import java.util.Scanner;
//华为OD机试 - 最长公共前缀（Java 2025 A卷 100分）
//https://blog.csdn.net/guorui_java/article/details/146975911

public class HC55Main {
    /**
     * 寻找字符串数组中的最长公共前缀 --HC55Main  -100分
     *
     * @param strs 字符串数组
     * @return 最长公共前缀，如果不存在则返回"@Zero"
     * 思路：横向扫描：
     * 首先确定第i个与第i+1个字符串子串相同的公共前缀K。
     * 将上面找到的前缀K与第i+2个子串进行对比，得到他们的公共前缀K1
     * 重复上述步骤，最终得到字符串的最长公共前缀
     * 时间复杂度：O(M*N) 其中 M 是字符串数组中的字符串的平均长度，N是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次
     */
    public static String longestCommonPrefix(String[] strs) {
        // 如果数组为空或null，返回"@Zero"
        if (strs == null || strs.length == 0) {
            return "@Zero";
        }

        // 以第一个字符串为基准
        String prefix = strs[0];

        // 逐个比较其他字符串 --找第0个和其他字符串的最长公共前缀
        for (int i = 1; i < strs.length; i++) {
            // 找到当前字符串与prefix的公共前缀
            int j = 0;
            while (j < prefix.length() && j < strs[i].length() && prefix.charAt(j) == strs[i].charAt(j)) {
                j++;
            }

            // i位置与prefix的公共前缀
            prefix = prefix.substring(0, j);

            // 如果公共前缀为空，直接返回"@Zero"
            if (prefix.length() == 0) {
                return "@Zero";
            }
        }

        return prefix;
    }

    /**
     * 主函数，用于读取输入并输出结果
     */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取输入字符串
        String input = scanner.nextLine();

        // 处理输入格式 [str1,str2,str3]
        input = input.substring(1, input.length() - 1); // 去掉前后的方括号
        String[] strs = input.split(",");

        // 调用函数并输出结果
        System.out.println(longestCommonPrefix(strs));

        scanner.close();
    }
}

